package 中等.双指针;

/**
 * 给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在
 *  相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，
 * 满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix
 * 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix
 * 或者 bprefix + asuffix 能否构成回文串。
 * 当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix
 * 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 
 * 和 "abc" + "" 都是合法分割。
 * 如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
 * 注意， x + y 表示连接字符串 x 和 y 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/split-two-strings-to-make-palindrome
 */
public class 分割两个字符串得到回文串_1616 {

    public static void main(String[] args) {

        checkPalindromeFormation("aejbaalflrmkswrydwdkdwdyrwskmrlfqizjezd",
                "uvebspqckawkhbrtlqwblfwzfptanhiglaabjea");

    }

    /**
     * 找规律+贪心+双指针
     * 依据题意，如果 a 的前 n 个字符，和 b 的后 n 个字符是
     * 回文串，且 a 或者 b 中 [n+1,b.len-n] 的中间部分也是回文串
     * 则能构成满足条件的回文串，b 的中间部分一定是以中心对称
     * 回文字符串，中间部分越短，越可能构造出回文字符串，就要
     * 使得 n 尽可能的大
     */
    public static boolean checkPalindromeFormation(String a, String b) {
        return check(a, b) || check(b, a);
    }

    private static boolean check(String a, String b) {
        int left = 0, right = a.length() - 1;

        while (left < right && a.charAt(left) == b.charAt(right)) {
            left++;
            right--;
        }
        return isPalindrome(a, left, right) || isPalindrome(b, left, right);
    }

    private static boolean isPalindrome(String str, int left, int right) {
        while (left < right && str.charAt(left) == str.charAt(right)) {
            left++;
            right--;
        }
        return right <= left;
    }

}
